|
A scale-free network is a network whose degree distribution follows a power law, at least asymptotically. That is, the fraction ''P''(''k'') of nodes in the network having ''k'' connections to other nodes goes for large values of ''k'' as : where is a parameter whose value is typically in the range 2 < < 3, although occasionally it may lie outside these bounds. Many networks have been reported to be scale-free, although statistical analysis has refuted many of these claims and seriously questioned others. Preferential attachment and the fitness model have been proposed as mechanisms to explain conjectured power law degree distributions in real networks. ==History== In studies of the networks of citations between scientific papers, Derek de Solla Price showed in 1965 that the number of links to papers—i.e., the number of citations they receive—had a heavy-tailed distribution following a Pareto distribution or power law, and thus that the citation network is scale-free. He did not however use the term "scale-free network", which was not coined until some decades later. In a later paper in 1976, Price also proposed a mechanism to explain the occurrence of power laws in citation networks, which he called "cumulative advantage" but which is today more commonly known under the name preferential attachment. Recent interest in scale-free networks started in 1999 with work by Albert-László Barabási and colleagues at the University of Notre Dame who mapped the topology of a portion of the World Wide Web, finding that some nodes, which they called "hubs", had many more connections than others and that the network as a whole had a power-law distribution of the number of links connecting to a node. After finding that a few other networks, including some social and biological networks, also had heavy-tailed degree distributions, Barabási and collaborators coined the term "scale-free network" to describe the class of networks that exhibit a power-law degree distribution. Amaral et al. showed that most of the real-world networks can be classified into two large categories according to the decay of degree distribution P(k) for large k. Barabási and Albert proposed a generative mechanism to explain the appearance of power-law distributions, which they called "preferential attachment" and which is essentially the same as that proposed by Price. Analytic solutions for this mechanism (also similar to the solution of Price) were presented in 2000 by Dorogovtsev, Mendes and Samukhin and independently by Krapivsky, Redner, and Leyvraz, and later rigorously proved by mathematician Béla Bollobás. Notably, however, this mechanism only produces a specific subset of networks in the scale-free class, and many alternative mechanisms have been discovered since. The history of scale-free networks also includes some disagreement. On an empirical level, the scale-free nature of several networks has been called into question. For instance, the three brothers Faloutsos believed that the Internet had a power law degree distribution on the basis of traceroute data; however, it has been suggested that this is a layer 3 illusion created by routers, which appear as high-degree nodes while concealing the internal layer 2 structure of the ASes they interconnect. 〔 〕 On a theoretical level, refinements to the abstract definition of scale-free have been proposed. For example, Li et al. (2005) recently offered a potentially more precise "scale-free metric". Briefly, let ''G'' be a graph with edge set ''E'', and denote the degree of a vertex (that is, the number of edges incident to ) by . Define : This is maximized when high-degree nodes are connected to other high-degree nodes. Now define : where ''s''max is the maximum value of ''s''(''H'') for ''H'' in the set of all graphs with degree distribution identical to ''G''. This gives a metric between 0 and 1, where a graph ''G'' with small ''S''(''G'') is "scale-rich", and a graph ''G'' with ''S''(''G'') close to 1 is "scale-free". This definition captures the notion of self-similarity implied in the name "scale-free". 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「Scale-free network」の詳細全文を読む スポンサード リンク
|